#include<iostream>
#include<vector>
using namespace std;

bool visit[20][20];
int ret;
int step;
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { 1, -1, 0, 0 };

void dfs(vector<vector<int>>& grid, int x, int y, int path)
{
	if (grid[x][y] == 2)
	{
		if (path == step)
		{
			ret++;
		}
		return;
	}

	int m = grid.size();
	int n = grid[0].size();

	for (int i = 0; i < 4; i++)
	{
		int x1 = x + dx[i];
		int y1 = y + dy[i];

		if (x1 >= 0 && x1 < m && y1 >= 0 && y1 < n && !visit[x1][y1] && grid[x1][y1] != -1)
		{
			visit[x1][y1] = true;
			dfs(grid, x1, y1, path + 1);
			visit[x1][y1] = false;
		}
	}

}
int uniquePathsIII(vector<vector<int>>& grid) 
{
	int x = 0;
	int y = 0;

	for (int i = 0; i < grid.size(); i++)
	{
		for (int j = 0; j < grid[0].size(); j++)
		{
			if (grid[i][j] == 0)
			{
				step++;
			}
			else if (grid[i][j] == 1)
			{
				x = i;
				y = j;
			}
		}
	}

	step += 2;
	visit[x][y] = true;
	dfs(grid, x, y, 1);

	return ret;
}

int main()
{
	vector<vector<int>> a = { {1,0,0,0},{0,0,0,0},{0,0,2,-1} };

	cout << uniquePathsIII(a) << endl;


	return 0;
}